home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 9 / CDACTUAL9.iso / share / Dos / VARIOS / pascal / SWAG9605.DDD / 0151_Infix to Postfix expression parser.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1996-05-31  |  5.4 KB  |  173 lines
  1. {
  2. I am trying to write an algorithm(in pseudocode or Pascal)  that
  3. converts a nonparenthesized infix expression to the equivalent postfix
  4. expression.
  5.  
  6. For example, the infix expression
  7.  
  8. 3 - 6 * 7 + 2 / 4 * 5 - 8
  9.  
  10. converts to the postfix expression
  11. ------ message termination by server was premature----
  12.  
  13. but postfix notation would be:  3 6 7 * - 2 4 / + 5 * 8 -
  14.  
  15. In the program that follows, the input is a character string which is
  16. then converted to a linked list. If numeric values are desired, the
  17. VAL function can be used at the time the list is made.
  18.  
  19. The advantage of the linked list approach is the ease with which the
  20. order of the terms may be rearranged. The disadvantage is the "write
  21. only" looking code that results--very un-Pascal like. Hopefully, the
  22. comments make it clearer.
  23.  
  24. The conversion of infix to postfix notation follows these rules:
  25.  
  26. 1. Multiplication and division take precedence over addition and
  27. subtraction.
  28.  
  29. 2. Where operations are of equal precedence, they are performed in
  30. sequential order from left to right.
  31.  
  32. The algorithm uses two linked lists. One is a queue, or FIFO, type
  33. list. Each node of this list is linked to the next and each node
  34. stores a "word" from the original math string in the same order as
  35. written. The other op linked list is a short list of one or two nodes
  36. which stores the math operations in order of their postfix execution.
  37. In both these lists, the last node points to nil. The math list is
  38. parsed from the front. Each operation is placed in the op list and
  39. removed from the longer list. The longer list is relinked and the op
  40. list is inserted in the proper position for postfix notation.
  41.  
  42. <clifpenn@airmail.net>   11:12PM  3/1/96
  43. --------------------------- }
  44.  
  45. Program InFixToPostFix;
  46. { Written in Turbo Pascal v6.0 by Clif Penn, Mar 1, 1996  }
  47.  
  48. Uses CRT;
  49. Label finis;
  50.  
  51. TYPE   link = ^node;   { link is a pointer to a node }
  52.        node = record
  53.             nxt:link;  { points to next node (or nil) }
  54.             dat:string[12];   {length of 12 is arbitrary}
  55.        end;
  56. VAR
  57. head, p1, p2, op:link;
  58. s, postfix:string;
  59.  
  60. Procedure MakeWrdList(ss:string);
  61. VAR
  62. wrd:string[12];   { 12 is arbitrary }
  63. s1, s2, len:integer;
  64. pt1, pt2:link;
  65.  
  66. Begin
  67.      pt1 := nil;
  68.      s1 := 1;
  69.      len := Length(ss);
  70.  
  71.      While s1 < len do
  72.      Begin
  73.           { skip spaces }
  74.           While (ss[s1] = ' ') AND (s1 < len) Do Inc(s1);
  75.           s2 := s1;   {start of word}
  76.           { parse to next space }
  77.           While (ss[s2] <> ' ') AND (s2 <= len) Do Inc(s2);
  78.           wrd := Copy(ss, s1, s2 - s1);   {extract wrd sans spaces}
  79.           s1 := s2;  {advance string index}
  80.  
  81.           pt2 := pt1;  {initially pt2 to nil, normally move down list}
  82.           new(pt1) ;   {get address for pt1 from heap}
  83.           if pt2 = nil then head := pt1;    {head-->first node}
  84.           pt2^.nxt := pt1;      {links old node to new}
  85.           pt1^.nxt := nil;      {last node in list points to nil}
  86.           pt1^.dat := wrd;      {stores wrd in node}
  87.      End;
  88.  
  89. { After above:  pt1 and pt2 no longer used
  90.          head-->[arg1]-->[op1]-->[arg2]-->[ .... ]-->nil       }
  91. End;
  92.  
  93. Procedure ShowList;
  94. VAR tmp:link;
  95. Begin
  96.      tmp := head;
  97.      postfix := '';
  98.      While tmp <> nil do
  99.      begin
  100.           postfix := postfix + tmp^.dat + ' ';  {concatanate string}
  101.           tmp := tmp^.nxt;  {traverse the list head to tail}
  102.      end;
  103.      Writeln(postfix);
  104. End;
  105.  
  106. Procedure InsertOp;
  107. {Inserts Op node(s) into PostFix linked list}
  108. Begin
  109.      p1^.nxt := op;  {insert op, the last op node points to nil}
  110.      While p1^.nxt <> nil do p1 := p1^.nxt;
  111.      p1^.nxt := p2^.nxt;  {remove p2 node from list}
  112.      p1 := p1^.nxt;  {last node of prev op now linked to list}
  113.      op := p2;       {new op becomes p2}
  114.      op^.nxt := nil;
  115.      p2 := p1;  {both now point to next argument}
  116. End;
  117.  
  118. Procedure ExtendOp;
  119. {Extracts math symbol node from PostFix list and extends Op list}
  120. Begin
  121.      p1^.nxt := p2^.nxt;    {remove p2 from list}
  122.      p1 := p1^.nxt;         {relink arg-->arg}
  123.      p2^.nxt := op;         {place p2 in front of old op}
  124.      op := p2;              {now op linked list has 2 nodes}
  125.      p2 := p1 ;             {both now point to next argument}
  126. End;
  127.  
  128. Procedure DoPostFix(st:string);
  129. Const
  130. Hi = ['*', '/'];   {Hi, Lo are math precedence rank of symbols}
  131. Lo = ['-', '+'];
  132.  
  133. Begin
  134.      MakeWrdList(st);
  135.      p1 := head;       {After this initialization, }
  136.      op := nil;        {p1, p2, arg1 --> arg2      }
  137.      p2 := p1^.nxt;    {op --> op1 --> nil         }
  138.      ExtendOp;
  139.  
  140.      While p2^.nxt <> nil Do    {last node points to nil}
  141.      Begin
  142.           p2 := p2^.nxt;  {p2 now pointing to math operation}
  143.           {Conditional char comparisons follow}
  144.           If (op^.dat[1] in Hi) OR (p2^.dat[1] in Lo) then
  145.                 InsertOp
  146.           Else  ExtendOp;
  147.      End;
  148.      p1^.nxt := op;  {links final math operation(s)}
  149. End;
  150.  
  151. BEGIN  {main program}
  152.      ClrScr;
  153.      Writeln('Just press Enter to quit.'); Writeln;
  154.      { Example }
  155.      s := '3 - 6 * 7 + 2 / 4 * 5 - 8';
  156.  
  157.      DoPostFix(s);
  158.      Writeln('In postfix notation, the infix string:');
  159.      Writeln(s, ' becomes:');
  160.      ShowList;
  161. Repeat
  162.      Writeln;
  163.      Writeln('Infix math string (spaces between everything):');
  164.      Readln(s);
  165.      If Length(s) < 5 then goto finis;
  166.  
  167.      DoPostFix(s);
  168.      ShowList;
  169. Until Length(s) < 5;
  170.  
  171. finis:
  172. END.
  173.